package leetcode_core.leetcode_4;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年11月01日 19:49
 */
public class MinFallingPathSum {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        memo = new int[n][m];
        for(int i = 0;i <n ;i++){
            Arrays.fill(memo[i],Integer.MAX_VALUE);
        }
        int res = Integer.MAX_VALUE;
        for(int j = 0;j <m ;j++){
            res = Math.min(res,dp(matrix,n-1,j,n,m));
        }
        return res;
    }
    private int[][] memo;
    private int dp(int[][] matrix,int i,int j,int n,int m){
        if(i < 0 || j < 0 || i >= n|| j >= m){
            //表示该路径不可达
            return Integer.MAX_VALUE;
        }
        //base-case
        if(i == 0){//回到最上层
            return matrix[0][j];
        }
        if(memo[i][j] != Integer.MAX_VALUE){
            return memo[i][j];
        }
        //状态转移
        memo[i][j] =  matrix[i][j]+Math.min(
                Math.min(dp(matrix,i-1,j,n,m),
                         dp(matrix,i-1,j-1,n,m)),
                         dp(matrix,i-1,j+1,n,m));
        return memo[i][j];
    }

}
